import time
import numpy as np

def matrixTraversal(M,target):
    row, col = M.shape
    flag = 0
    for i in range(row):
        for j in range(col):
            if M[i][j] == target:
                return 1,i,j
    return flag,-1,-1

def matrixSearch(M,target):
    row, col = M.shape
    flag = 0
    for idx in range(min(row,col)+1):
        if idx == min(row,col):
            break
        if M[idx][idx] >= target:
            break
    if idx == 0:
        return flag,-1,-1
    if idx < min(row,col)-1:
        for i in range(idx+1):
            if M[i][idx] == target:
                flag = 1
                return flag,i,idx
            elif M[idx][i] == target:
                flag = 1
                return flag,idx,i
    elif idx == min(row,col)-1:
        for i in range(max(row,col)):
            if M[min(i,row-1)][idx] == target:
                return 1,i,idx
            elif M[idx][min(i,col-1)] == target:
                return 1,idx,i
    else:
        idx -= 1
        if row < col:
            for i in range(0,row):
                for j in range(idx,col):
                    if M[i][j] == target:
                        return 1,i,j
        else:
            for i in range(idx,row):
                for j in range(0,col):
                    if M[i][j] == target:
                        return 1,i,j
    return flag,-1,-1
        


if __name__ == "__main__":
    M = [[1, 4, 7, 11, 15],
        [2, 5, 8, 12, 19],
        [3, 6, 9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30]]
    M = np.array(M)
    # M = np.arange(10000).reshape(100,100)
    print(M)
    target = 20

    start1 = time.time()
    flag, row, col = matrixTraversal(M,target)
    print(row,col)
    end1 = time.time()
    print('"Traversal" cost ',end1-start1,'\n')

    start2 = time.time()
    flag, row, col = matrixSearch(M,target)
    print(row,col)
    end2 = time.time()
    print('"my algorithm" cost ',end2-start2,'\n')

    start3 = time.time()
    idx = np.where(M==target)
    print(idx)
    end3 = time.time()
    print('"np.where" cost ',end3-start3,'\n')

